1. Field of the Invention
The present invention relates to an apparatus for correcting an error occurred in a communication path in a digital communication system or a recording medium in a digital recording system, at a receiving or reading station.
2. Related Background Art
In the digital communication system and the digital recording system, an error correcting code has been used to correct an error occurred in the communication path or the recording medium at the receiving station. As such an error correcting code, Reed-Solomon code (RS code) and BCH code have been well known. Those codes are widely utilized in an optical disk and a satellite communication and encoder and decoder therefor have been implemented in the form of IC.
Recently, a decoder having a high error correcting capability at a high speed is demanded and various proposals have been made to meet this demand. Before explaining the proposals specifically, assuming that an RS code is used as an error correcting code, a formula expressing a received word R(x) is first explained. The following generator polynomial is used: ##EQU1## where m (a positive integer) represents a bit length of one symbol, n.ltoreq.2.sup.m-1 represents a code length, k=n-(d-1) represents an information length and d represents a minimum distance.
For simplicity, it is assumed that b=0 in the formula (1), the code is defined on a Galois field GF(2.sup.m) and a primitive element thereof is at .alpha.. The encoding is carried out by the following operation.
A check polynomial P(x) is generated from the following polynomial I(x) having coefficients represented by an information string {I.sub.k-1, I.sub.k-2, . . . , I.sub.0 } and the generator polynomial G(x) of the formula (1): ##EQU2## A code word C(x) transmitted is represented by: EQU C(x)=I(x).multidot.X.sup.d-1 +P(x) (4)
where in the formula (4) deg P(x)&lt;n-k represents an order of P(x) and a coefficient of P(x) gives a check digit.
It is assumed that when the code word represented by the formula (4) is transmitted, an error E(x) is added in a communication path and a received word R(x) represented by the following formula (5) is received at a receiving station, wherein the coefficients of E(x) are also represented by the Galois field GF(2.sup.m) and are zero if there is no error. EQU R(x)=C(x)+E(x) (5)
Various methods have been proposed as a decoding method for the received word R(x) of the RS code, and U.S. Pat. No. 4,873,688 discloses a decoder having a configuration principle as shown in FIG. 7. In this decoder, a received word R.sub.n-j is inputted to a syndrome polynomial operation circuit 1, which operates a syndrome polynomial S(x) by the following formula (6). ##EQU3## where ##EQU4##
The syndrome polynomial S(x) is inputted to polynomial operation circuits 4 and 5 and an error locator polynomial .sigma.(x) and a differentiation thereof .sigma.'(x) and an error evaluator polynomial .omega.(x) are determined in the course of an operation of an Euclidean algorithm. Then, the error locator polynomial .sigma.(x), the differentiation thereof .alpha.'(x) and the error evaluator polynomial .omega.(x) are inputted to polynomial processing circuits 6a-6c where x is set to .alpha..sup.i and the formulas thus processed are inputted to a correction circuit 7.
In the correction circuit 7, if the error locator polynomial .sigma.(.alpha..sup.i) is 0, it is determined that an error has occurred in an i-th symbol R.sub.i of the received word and the error evaluator e.sub.i is calculated by the following formula: EQU e.sub.i =.omega.(.alpha..sup.i)/.sigma.'(.alpha..sup.i) (8)
In FIG. 7, since the processing in the polynomial operation circuits 4 and 5 and the processing in the polynomial processing circuits 6a-6c can be concurrently carried out, pipeline processing is carried out for the continuously transmitted received words (messages 1, 2, 3, . . . ) as shown in FIG. 9. In actual, a memory M is provided as shown in FIG. 8 and it receives the received word in synchronism with the processing of the syndrome polynomial operation circuit 1 and outputs it in synchronism with the processing of the correction circuit 7 to carry out the decoding at a high speed on real time basis.
In this manner, if the error locator polynomial .sigma.(.alpha..sup.i) is 0, it is assumed that an error has occurred in the i-th symbol R.sub.i of the received word and a correction value p.sub.i =e.sub.i is added to the symbol R.sub.i to correct the i-th symbol R.sub.i of the received word.
In the proposed decoder, 16 errors can be corrected at a rate of 80M bits/sec (bps) on real time basis but it cannot carry out erasure correction.
On the other hand, the inventor of the present invention have proposed a decoder for carrying out the decoding operation including the erasure correction (U.S. Pat. No. 5,325,373) and FIG. 10 shows a block diagram of a configuration principle of the proposal.
In the proposed decode, an erasure locator polynomial operation circuit 2 and a product polynomial operation circuit 3 are newly provided, and in the erasure locator polynomial operation circuit 2, an erasure location polynomial .lambda.(x) shown by the following formula (9) is calculated: ##EQU5## where Y(i)=.alpha..sup.ji (i=1, 2, . . . , s) for s erasure locations j.sub.1, j.sub.2, . . . j.sub.s.
In this case, it is assumed that s erasures occur at locations j.sub.1, j.sub.2, . . . j.sub.s in the received word R(x), r errors occurs in addition to the erasure at locations k.sub.1, k.sub.2, . . . k.sub.r, and the decoder is aware of the erasure locations j.sub.1, j.sub.2, . . . j.sub.s but unaware of the error locations k.sub.1, k.sub.2, . . . k.sub.r. It is assumed that the erasure is indicated by a flag and a symbol of the erasure location is a dimension on the Galois field GF(2.sup.m) as other locations are. It is also assumed that 2t+s+1.ltoreq.d (where t represents the number of correctable errors and t.gtoreq.r) is met.
The syndrome polynomial S(x) calculated by the syndrome polynmial operation circuit 1 and the erasure locator polynomial .lambda.(x) are inputted to the product polynomial operation circuit 3 in the same manner as in the decoder of FIG. 7, and in the product polynomial operation circuit 3, the product polynomial M(x)=S(x).multidot..lambda.(x) of the syndrome polynomial S(x) and the erasure locator polynomial .lambda.(x) is calcuated. The product polynomial M(x)=S(x).multidot..lambda.(x) is then inputted to the polynomial operation circuit 4, and in the polynomial operation circuits 4 and 5, an error locator polynomial .sigma.(x) and an error evaluator polynomial .omega. which meet the following formulas (10) and (11) are calculated for the polynomial x.sup.d-1 and the product polynomial M(x): EQU deg .omega.(x)&lt;t+s, deg .sigma.(x).ltoreq.t (10) EQU A(x).multidot.X.sup.d-1 +.sigma.(x).multidot.M(x)=.omega.(x)(11)
where A(x) is a polynomial on the GF(2.sup.m).
The error evaluator polynomial .omega.(x) and the error locator polynomial .sigma.(x) which meet the formulas (10) and (11) are determined by separate processing in the course of the Euclidean algorithm to determine a greatest common divisor polynomial (GCD) of x.sup.d-1 and M(x).
Then, the error evaluator polynomial .omega.(x), the error locator polynomial .sigma.(x), the differentiation .sigma.'(x) of the error locator polynomial .sigma.(x), the erasure locator polynomial .lambda.(x) and the differentiation .lambda.'(x) of the erasure locator polynomial .lambda.(x) are inputted to the polynomial processing circuits 6a-6e and x is set to .alpha..sup.i (i=-n+1, . . . , 0) in those formulas. The error evaluator polynomial .omega.(.alpha..sup.i), the error locator polynomial .sigma.(.alpha..sup.i), the differentiation .sigma.'(.alpha..sup.i) of the error locator polynomial .sigma.(x), the erasure locator polynomial .lambda.(.alpha..sup.i) and the differentiation .lambda.'(.alpha..sup.i) of the erasure locator polynomial .alpha.(x) are inputted to the correction circuit 7.
In the correction circuit 7, if the error locator polynomial .sigma.(.alpha..sup.i) is 0, it is determined that an error occurred in the i-th symbol R.sub.i of the received word and the error e.sub.i is calculated by the following formula (12) and an erasure value E.sub.i at the erasure location is calculated by the following formula (13): EQU e.sub.i =.omega.(.alpha..sup.i)/{.sigma.'(.alpha..sup.i).multidot..lambda.(.alpha. .sup.i)} (12) EQU E.sub.i =.omega.(.alpha..sup.i)/{.lambda.'(.alpha..sup.i).multidot..sigma.(.alpha. .sup.i)} (13)
In this manner, the correction value p.sub.i is added to the i-th symbol R.sub.i of the received word determined to have the error to correct the error and fill the erasure in order to correct the received word where the correction value is represented by: EQU p.sub.i =e.sub.i ; when the error locator polynomial .sigma.(.alpha..sup.i) is 0 (14a) EQU p.sub.i =E.sub.i ; when erasure location (14b) EQU p.sub.i =0; other cases (14c)
In this manner, the decoding operation including the erasure correction can be carried out by the decoder previously proposed by the present inventors.
The proposed decoder can carry out the decoding operation including the erasure correction but a circuit scale of the decoder and a processing time increase and the high speed real time processing as disclosed in U.S. Pat. No. 4,873,688 is difficult to attain.